BOJ_1753_최단경로

다익스트라(Dijkstra) 알고리즘을 사용해서 시작점 K부터 모든 노드의 최단 경로를 구하는 문제

다익스트라의 전형으로 볼 수 있다. 내 기준 조금 낯선 것은 중복 간선을 허용한다는 것이다
예를 들어 1에서 2로 가는 가중치가 9, 3, 7 이렇게 들어올 수도 있다. 하지만 다익스트라의 원리 상 중복 간선이 있어도 하등 문제 없다. 어차피 더 짧은 간선을 탐색하게 된다.

보통 다익스트라는 배열 안에 리스트를 둬서 거기에 [다음 노드 번호, 가중치]를 저장하는 식으로 구성된다.(파이썬은 리스트 안에 리스트)

이 문제도 무난하게 그렇게 풀면 된다

딕셔너리

파이썬에서는 딕셔너리로 그래프를 구성할 수 있다고 한다. 2차원 딕셔너리를 구성해 node1(key1) > node2(key2) > value 방식으로 구성을 한다면 조회/갱신에서 ==O(1)==의 시간복잡도를 갖기 때문에 효율적이다.

파이썬 딕셔너리 한 번도 안 써봐서 딕셔너리 쓰는 코드는 좀 찾아보면서 했다

{1: {2: 3, 3: 5, 4: 2}, 2: {3: 4}, 3: {4: 1}}

이런 식으로 구성되며, dic[a][b]에 가중치를 넣어주면 된다

나머지는 일반적인 다익스트라와 똑같다

딕셔너리와 리스트 비교

이 문제처럼, 정점이 1부터 V까지 번호가 연속되어 매겨져 있는 경우, 중복 간선이 존재하는 경우에는 리스트가 유리하다.

메모리 사용
리스트의 경우 연속된 메모리 블록을 사용하지만, 딕셔너리는 해시 테이블 구조로 더 많은 메모리를 사용한다

정점의 번호
리스트는 1부터 V까지의 정점 번호를 인덱스로 사용할 수 있다
반면 딕셔너리는 연속된 번호라고 해도 해시 함수를 계산해야 한다

중복 간선 허용
딕셔너리에서는 두 노드를 키로 하는 유일한 가중치를 가지기 때문에 만일 중복 간선이 있다면 업데이트 해줘야 한다
반면 리스트는 중복 간선을 고려할 필요 없이 기존처럼 (연결된 노드, 가중치)를 넣어주면 된다. 다익스트라 알고리즘을 통해 가중치가 작은 노드로 경로를 만들어진다.

추가로, 동일한 O(1)이지만 조회 속도도 약간 차이가 있다고 한다.

조회 속도
연속된 정점이라면 인덱스 = V 이기 때문에 리스트에서는 인덱스 접근으로 O(1)이 소요된다.
딕셔너리도 마찬가지로 O(1)이다. 그치만 실제로는 리스트보다 약간 느릴 수 있다고 한다.

딕셔너리 그래프는 언제 유용할까?

리스트의 장점을 살리지 못하는 경우에는 딕셔너리가 유리하다고 할 수 있다.
예를 들어 정점 번호가 연속적이지 않거나, 문자열이거나, 매우 큰 값일 때 라던지
중간에 정점이 추가되거나 제거되는 경우가 있을 때는 딕셔너리가 유용할 수 있다

# 시작점에서 다른 모든 정점으로의 최단 경로 && 가중치 자연수 : 다익스트라  
import sys  
from heapq import heappush, heappop  
from collections import defaultdict  
  
V, E = list(map(int, input().split()))  
K = int(input())  # 시작 정점  
  
graph = defaultdict(dict)  
  
# 입력  
for i in range(E):  
    u, v, w = map(int, input().split())  
  
    if v not in graph[u] or graph[u][v] > w:  
        graph[u][v] = w  
  
# 최단 탐색  
d = [sys.maxsize] * (V + 1)  
d[K] = 0  
  
  
def dijkstra():  
    hq = list()  
    heappush(hq, (0, K))  
  
    while hq:  
        dist, num = heappop(hq)  
  
        if dist > d[num]:  
            continue  
  
        for next_node, value in graph[num].items():  
            if d[num] + value < d[next_node]:  
                d[next_node] = d[num] + value  
                heappush(hq, (d[next_node], next_node))  
  
  
dijkstra()  
  
for dis in d[1:]:  
    if dis == sys.maxsize:  
        print("INF")  
  
    else:  
        print(dis)